The present invention relates to a method for correction of errors in a binary word stored in multi-level memory cells, with minimum number of correction bits.
In order to detect and correct errors in a binary word which contains m bits, which is indicated hereinafter as a source word, techniques are known which are based on the addition of xe2x80x9credundancyxe2x80x9d to the source word, i.e., techniques based on the association with the source word, and consequent storage, of a binary word which contains k bits, and is indicated hereinafter as the correction word, in which the k bits are obtained by carrying out k parity checks on k sub-groups selected appropriately from the m bits in the source word.
This association is carried out in the so-called coding process, in which the 2m possible source words, which can be defined by means of m bits, are mapped in a set of an equivalent number of binary words of m+k bits, which are indicated hereinafter as the code words, each of which can be obtained by disposing a source word and the corresponding correction word one after the other and is then stored in the memory.
The value of each of the k correction bits associated during the coding process, depends on the type of parity check carried out. For example, the values of the k correction bits can be associated according to the so-called even parity checking criterion, i.e., the logic value 0 or 1, according to whether in the i-th sub-group there is respectively an even or odd number of logic values 1, is associated with the bit in the i-th position in the correction word, or the values can be associated according to the so-called odd parity checking criterion, i.e., the logic value 0 or 1, according to whether in the i-th sub-group there is respectively an odd or even number of logic values 1, is associated with the bit in the i-th position in the correction word.
The decoding process, in which, on the basis of a code word containing m+k bits stored, there is determination of the corresponding source word with m bits, with detection and correction of any errors which have been generated in it during the storage period, is carried out by executing once again the k parity checks on the bits in the source word, and comparing the correction word thus obtained with the correction word which is read by the memory, in order to generate a check word, which is also of the binary type and indicates the position of the error(s) present in the source word.
In detail, in the decoding process the i-th bit in the correction word, which is obtained by executing the i-th parity check on the i-th sub-group of the binary source word, is compared with the bit which is present in the i-th position in the correction word read by the memory and the logic value 0 or 1, according to whether the two bits compared are respectively the same as one another or different, is then associated with the i-th bit in the check word.
The check word is then compared with a plurality of error codes, each of which is constituted by a binary word which has the same length as the check word, and is associated with a bit or a group of bits in the source word and in the correction word, and is thus indicative of the position of this bit or group of bits. If there is an error, the check word is identical to one of the error codes, and thus, by means of the said association, it is possible to identify the incorrect bit(s).
With the bits in an error code having the logic value 1, there is associated a meaning which is linked to the composition of the sub-groups in the source word, of which the parity is to be checked.
In particular, a bit which is at the logic level 1 in the i-th position in the error code is indicative of the fact that the bit in the source word, which is located in the position associated with this error code, is part of the i-th sub-group of bits in the source word, on which the i-th parity check is carried out.
For example, in the case of the error code xe2x80x9c0101xe2x80x9d and on the assumption that this is associated with the error in the first bit in the source word, this error code is indicative of the fact that the first bit in the binary source word must form part of the sub-groups of bits on which the first and third parity checks are carried out.
In fact, by this means, if the first bit in the source word is incorrect, both the first bit and the third bit in the correction word which is generated during decoding (obtained from the first and the third parity checks) are different from the corresponding bits in the correction word generated during coding (during which the bit was different), and thus the error code which is obtained by comparing the two correction words has both the first and the third bit set to the logic value 1.
If the k sub-groups in the source word on which the k parity checks are to be carried out are selected appropriately, the error code is in bi-univocal correspondence with the position, within the code word, of the single incorrect bit(s) and thus when this bi-univocal correspondence is known the incorrect bit(s) can be corrected.
If conventional memories are used, in which a single bit is stored in each memory cell, the malfunctioning of a memory cell gives rise to deterioration of a single bit.
If, as is usually the case for this type of memory, the probability of failure of a cell is relatively low, it is sufficient to use a correction code which can detect and correct a single error in the source word; in fact, the probability of occurrence of a plurality of errors within the source word is negligible.
On the other hand, in a multi-level memory, in which several bits are stored in each memory cell, the malfunctioning of even a single memory cell can give rise to a multiple error, i.e., an error in several bits simultaneously.
In fact, as is known, in a floating gate multi-level memory cell the data to be stored is associated with the quantity of electric charge which is stored in the floating gate region (which in turn defines the value of the threshold voltage of the memory cell) and thus the loss or gain of electric charges in the floating gate region of one of the memory cells which is used in order to store the code word can generate, within the code word, a maximum number of errors which is equivalent to the number n of bits stored in the memory cell in which the deterioration of the electric charge has taken place.
In order to be efficient, a method for correction of the errors in a multi-level memory thus makes it necessary to be able to detect and correct multiple errors.
By using the known methods for the correction of multiple errors, there would be a considerable increase in the number of bits in the correction word, for the same length of source word, compared with the number required for correction of a single error, and thus an increase in the memory area, for the same data storage capacity.
It should however be noted that the deterioration of the electric charge stored in the floating gate region of a multi-level memory cell means that the n possible errors which this deterioration generates within the code word are present in positions which are correlated to one another and are known on the basis of the law of association, established a priori in the memory design stage, according to which the bits in the code word have been stored in the memory cells.
If, for example, in each memory cell there are stored n bits, which are disposed in adjacent positions in the binary word, the n possible errors generated by the faultiness of this memory cell can also only be disposed in positions which are adjacent within the binary word.
In order to correct a single error and dual errors present in any positions which are non-correlated to one another, within a code word stored in a conventional memory, for a binary word with m bits to be stored there is required a number k of correction bits such that the following inequality is fulfilled:
2k greater than 1+m+k+xc2xdxc2x7(m+k)xc2x7(m+kxe2x88x921)xe2x80x83xe2x80x831)
The preceding inequality simply expresses the fact that it must be possible to put the 2k possible correction words which can be generated with k bits into bi-univocal correspondence with the m+k possible positions of a single error and with the (m+k)(m+kxe2x88x921)/2 possible combinations of the positions of two errors; the additional 1 is derived from the fact that it is also necessary to take into consideration the condition of lack of errors.
From 1) it can easily be deduced that in order to correct a single error within the code word the following inequality must be fulfilled:
2k greater than 1+m+kxe2x80x83xe2x80x832)
On the other hand, for the correction of two errors in positions which are correlated within the code word stored in a multi-level memory, in which 2 bits are stored in one memory cell, for a source word with m bits there is required a number k of correction bits such that the following inequality is fulfilled:                               2          k                 greater than                   1          +                                    3              2                        ·                          (                              m                +                k                            )                                                          3        )            
which can be deduced from the inequality 1), taking into account the fact that the possible combinations of the positions of two errors in correlated positions are only (m+k)/2.
In general, for correction of r errors in positions which are correlated within a code word stored in a multi-level memory, in which 2 bits are stored in one memory cell, for a binary word with m bits to be stored there is required a number k of correction bits such that the following inequality is fulfilled:                               2          k                 greater than                   1          +                                                                      2                  xe2x80x2                                -                1                            r                        ·                          (                              m                +                k                            )                                                          4        )            
For the most significant values of m, the table in FIG. 1 shows the minimum values of k which are required for correction of two errors in any positions, of two errors in adjacent positions, and of a single error, if two bits are stored in each memory cell.
Examination of this table shows that the correction of two errors in correlated positions can be carried out using the same number of additional cells required for the correction of a single error, at least for binary words which have lengths longer than 8 bits.
In particular, analysis of the last two lines of the table shows that in order to carry out the correction of two errors in correlated positions, in the case of a 32-bit binary word (16 cells), it would be necessary to use 6 correction bits (3 cells), with an increase of 19% in the memory matrix area, whereas in order to carry out the correction of two errors in correlated positions, in the case of a 64-bit binary word (32 cells), it would be necessary to use 7 correction bits (4 cells), with an increase of only 12.5% in the memory matrix area.
The foregoing information, provided with reference to the case of two errors in correlated positions, is also valid for the general case of n errors in correlated positions, and this shows immediately that the correlation between the position of the errors within the source word is in general a condition which minimizes the number of correction bits necessary (and thus the number of additional correction cells), which can be calculated by means of the inequality 3) in the case of any n, or by means of the inequality 4) in the case of n=2.
However, in the literature there are not known criteria of definition of the k sub-groups of the source word on which there can be carried out the k operations of checking of parity, in the case of correction of multiple errors in correlated positions, in which there is met the condition of bi-univocality of the correspondence between the error code and the position of the single incorrect bit or the n incorrect bits.
An embodiment of the present invention provides a method for correction of errors in a binary word stored in multi-level memory cells, which fulfills the condition of requiring the minimum number of correction bits and the condition of complying with the bi-univocality of the correspondence between the error code and the position of the single incorrect bit or the n incorrect bits.